package com.laotang.第_14_章_贪心算法.力扣_452_用最少数量的箭引爆气球;


import java.util.Arrays;
import java.util.Comparator;

public class _452_minimum_number_of_arrows_to_burst_balloons {
    // 按照区间起点升序排列
    public int findMinArrowShots1(int[][] points) {
        if (points.length <= 1) return points.length;

        // 按照区间的左边界升序排列
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] p1, int[] p2) {
                if (p1[0] < p2[0]) {
                    return -1;
                } else if (p1[0] > p2[0]) {
                    return 1;
                }
                return 0;
            }
        });

        int res = 1;
        // 将第一个区间设置为可射区间
        int[] range = new int[]{points[0][0], points[0][1]};

        for (int i = 1; i < points.length; i++) {
            int[] curr = points[i];
            if (curr[0] <= range[1]) {
                range[0] = Math.max(range[0], curr[0]);
                range[1] = Math.min(range[1], curr[1]);
            } else {
                res++;
                range[0] = curr[0];
                range[1] = curr[1];
            }
        }

        return res;
    }

    // 按照区间终点升序排列
    public int findMinArrowShots(int[][] points) {
        if (points.length <= 1) return points.length;

        // 按照区间的右边界升序排列
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] p1, int[] p2) {
                if (p1[1] < p2[1]) {
                    return -1;
                } else if (p1[1] > p2[1]) {
                    return 1;
                }
                return 0;
            }
        });

        int res = 1;
        int pos = points[0][1];
        for (int i = 1; i < points.length; i++) {
            int[] curr = points[i];
            if (curr[0] > pos) {
                res++;
                pos = curr[1];
            }
        }

        return res;
    }
}
